17. 电话号码的字母组合
17. 电话号码的字母组合
分析
77. 组合 是从同一个集合 m 中取 n 个元素进行组合，m<n，且元素不能重复，而这道题是从 m 个不同的集合中取 m 个元素进行组合，每个集合取出来一个元素，不用考虑元素重复的问题，更简单。
方法是，循环每一个位置上的所有可能即可，方法是用 for 循环嵌套，每一层 for 循环的变量都代表每一个位置上的所有可能的元素。
不过这里有两个优化的点：
- 获取字符串的每一个字符，因为我们知道这个字符对应的数字是 1-9，所以可以直接用这个字符减去 '0' 来计算这个字符对应的 int 类型的额数字，原理是，每一个字符都有一个 ASCII码，比如 '0' 的码就是 48，'1' 的码是 49，以此类推，当我们用减号处理两个 char 字符的时候，char 字符会自动转化为对应的 ASCII 码进行计算，因此，我们通过计算字符与 '0' 的距离就可以计算出这个字符对应的数字，这个比
Integer.valueOf(""+charObj);要快非常多。 我们在 76. 最小覆盖子串 中也学习过 char 到 ASCII 码的转化。 - 不要使用 String，尽量使用
StringBuilder，注意，不能无脑用 String 字符串拼接，性能会慢好几倍，因此能用 StringBuilder 的地方一定要用 StringBuilder。我们在 257. 二叉树的所有路径 中也遇到过这个小优化性能有问题。
解题
public char[][] mappping = new char[][]{{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
public List<String> result = new ArrayList<>();
public List<String> letterCombinations(String digits) {
char[] chars = digits.toCharArray();
if(chars.length==0){
return result;
}
getCombination(chars,0,new StringBuilder(""));
return result;
}
public void getCombination(char[] source ,int index,StringBuilder comb){
if(index == source.length){
result.add(comb.toString());
return;
}
char c = source[index];
// 直接通过减去 '0' 这个字符，实际上是减去 '0' 的 ASCII 码来快速确定 int 值
int num = c-'0';
// 保证num 一定是2-9
if(num<2 ||num >9){
return;
}
// 注意这里是减2，数字减一之后，从数字变索引，还要减一
char[] chars = mappping[num-2];
for(int i=0;i<chars.length;i++){
comb.append(chars[i]);
getCombination(source,index+1,comb);
comb.deleteCharAt(comb.length()-1);
}
}